The \emph{domination subdivision number} sd$(G)$ of a graph $G$ is theminimum number of edges that must be subdivided (where an edge can besubdivided at most once) in order to increase the domination number of $G$. Ithas been shown \cite{vel} that sd$(T)\leq 3$ for any tree $T$. We prove thatthe decision problem of the domination subdivision number is NP-complete evenfor bipartite graphs. For this reason we define the \emph{dominationmultisubdivision number} of a nonempty graph $G$ as a minimum positive integer$k$ such that there exists an edge which must be subdivided $k$ times toincrease the domination number of $G$. We show that msd$(G)\leq 3$ for anygraph $G$. The domination subdivision number and the dominationmultisubdivision numer of a graph are incomparable in general case, but we showthat for trees these two parameters are equal. We also determine dominationmultisubdivision number for some classes of graphs.
展开▼
机译：图$ G $的\ emph {支配细分数} sd $（G）$是为了增加$ G $支配数必须细分的最小边数（一条边最多可以细分一次）。 。已经显示\ cite {vel}表示任何树$ T $ sd $（T）\ leq 3 $。我们证明即使对于二部图，控制细分数的决策问题也是NP完全的。因此，我们将非空图$ G $的\ emph {dominationmultisubvision编号}定义为最小正整数$ k $，以便存在必须将$ k $细分的边以增加$ G $的控制数。我们显示任何图形$ G $的msd $（G）\ leq 3 $。一般情况下，图的支配细分数和支配细分数是不可比的，但是我们证明对于树，这两个参数是相等的。我们还为某些类的图确定dominationmultisubvision数。
展开▼
